#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    /**
     * @brief 枚举奇偶坐标分别排序
     *
     * @param nums
     * @return vector<int>
     */
    vector<int> sortEvenOdd(vector<int> &nums)
    {
        int n = nums.size();
        if (3 > n)
        {
            return nums;
        }

        vector<int> evenNums, oddNums;
        for (size_t i = 0; i < n; i++)
        {
            if (i % 2 == 0)
            {
                evenNums.emplace_back(nums[i]);
            }
            else
            {
                oddNums.emplace_back(nums[i]);
            }
        }

        // sorted
        // 偶数坐标 非递减 - 升序
        sort(evenNums.begin(), evenNums.end());
        // 奇数坐标 非递增 - 降序
        sort(oddNums.rbegin(), oddNums.rend());
        int e = 0, o = 0;
        for (size_t i = 0; i < n; i++)
        {
            if (i % 2 == 0)
            {
                nums[i] = evenNums[e++];
            }
            else
            {
                nums[i] = oddNums[o++];
            }
        }
        return nums;
    }

    vector<int> sortEvenOdd(vector<int> &nums)
    {
        vector<int> odd, evn, res(nums.size());
        for (int i = 0; i < nums.size(); ++i)
        {
            if (i % 2 == 0)
                evn.push_back(nums[i]);
            else
                odd.push_back(nums[i]);
        }
        sort(odd.begin(), odd.end(), greater<int>());
        sort(evn.begin(), evn.end());
        for (int i = 0; i < nums.size(); ++i)
        {
            if (i % 2 == 0)
                res[i] = evn[i / 2];
            else
                res[i] = odd[i / 2];
        }
        return res;
    }
};
int main()
{
    Solution s;
    vector<int> nums = {36, 45, 32, 31, 15, 41, 9, 46, 36, 6, 15, 16, 33, 26, 27, 31, 44, 34};
    vector<int> ret = s.sortEvenOdd(nums);
    for (auto &v : ret)
    {
        cout << v << " ";
    }
    cout << endl;
    return 0;
}